// 可以用r、e、d三种字符拼接字符串，如果拼出来的字符串中
// 有且仅有1个长度>=2的回文子串，那么这个字符串定义为"好串"
// 返回长度为n的所有可能的字符串中，好串有多少个
// 结果对 1000000007 取模， 1 <= n <= 10^9
// 示例：
// n = 1, 输出0
// n = 2, 输出3
// n = 3, 输出18
public class RedPalindromeGoodStrings {
    public static int num1(int n){
        char[] path = new char[n];
        return f(path,0);
    }

    public static int f(char[] path, int i){
        if(i == path.length){
            int cnt = 0;
            for(int l = 0; l < path.length; l++){
                for(int r = l + 1; r < path.length; r++){
                    if(check(path,l,r)){ //判断字串是否为回文结构
                        cnt++;
                    }
                    if(cnt > 1){  //只允许字符串中的字符串只有一个回文串，超过就不是好串
                        return  0;
                    }
                }
            }
            return cnt;
        }
        //正常位置
        int ans = 0;
        path[i] = 'r';
        ans += f(path,i+1);

        path[i] = 'e';
        ans += f(path,i+1);

        path[i] = 'd';
        ans += f(path,i+1);

        return ans;
    }

    public static boolean check(char[] path, int l, int r){
        while(l < r){
            if(path[l++] != path[r--]){
                return false;
            }
        }
        return true;
    }


    public static void main(String[] args) {
        //打表找规律
        for(int i = 1; i <= 100; i++){
            System.out.println(i + ": " +num1(i));
        }
    }
    //找出规律0，3，18，30，36，42，48...
    //i>=4的时候没多一个数，就增加6个好串

    public static int num2(int n){
        if(n == 1){
            return 0;
        }
        if(n == 2){
            return 3;
        }
        if(n == 3){
            return 18;
        }

        return (int) (((long)(n+1) * 6)) % 1000000007;
    }
}
